package com.zzg.algorithm.dijkstra;


import com.zzg.algorithm.dijkstra.entity.Graph;

/**
 * @Author zhengzg
 * @Date 2022-10-10
 * @Version v1.0
 * 迪杰斯特拉算法：最短路径问题
 * 1) 战争时期，胜利乡有 7 个村庄(A, B, C, D, E, F, G) ，现在有六个邮差，从 G 点出发，需要分别把邮件分别送到 A, B, C , D, E, F 六个村庄
 * 2) 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里
 * 3) 问：如何计算出 G 村庄到 其它各个村庄的最短距离?
 * 迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。
 * 它的主要特点是以 起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
 */
public class DijkstraAlgorithm {
    public static void main(String[] args) {
        char[] vertex = {'A', 'B', 'C', 'D', 'E', 'F', 'G'};
        //邻接矩阵
        int[][] matrix = new int[vertex.length][vertex.length];
        final int N = 65535;
        // 表示不可以连接
        matrix[0] = new int[]{N, 5, 7, N, N, N, 2};
        matrix[1] = new int[]{5, N, N, 9, N, N, 3};
        matrix[2] = new int[]{7, N, N, N, 8, N, N};
        matrix[3] = new int[]{N, 9, N, N, N, 4, N};
        matrix[4] = new int[]{N, N, 8, N, N, 5, 4};
        matrix[5] = new int[]{N, N, N, 4, 5, N, 6};
        matrix[6] = new int[]{2, 3, N, N, 4, 6, N};
        // 创建Graph对象
        Graph graph = new Graph(vertex, matrix);
        graph.showGraph();
        graph.dsji(2);
        graph.show();
    }
}
